class Solution {
public:
	int countPrimes(int n) 
	{
		vector<int> IsPrimer(n, 1);   
		int ans = 0;
		for (size_t i = 2; i < n; i++)
		{
			if (IsPrimer[i])
			{
				ans++;
				if ((long long)i * i < n)
				{
					for (size_t j = i * i; j < n; j = j + i)
					{
						IsPrimer[j] = 0;
					}
				}
			}
		}
		return ans;
	}
};